%
%~~
%~~  Aspectos Conceituais
%~~
%
\chapter{Aspectos Conceituais}
\label{02:chp:aspectosconceituais}

Nesta seção apresentam-se os conceitos teóricos fundamentais utilizados na metodologia do projeto. Explica-se a teoria de cobertura dos conjuntos, a seguir, detalhes sobre a descoberta de conhecimento em base de dados, e uma especificação sobre as técnicas que serão utilizadas para a mineração de dados. A fim de proporcionar um melhor entendimento, alguns tópicos serão abordados dentro do contexto de um sistema de diagnóstico médico, que é o escopo do projeto.

\section{Cobertura de Conjuntos em Problemas de Diagnóstico}
\label{01:sec:coberturaconjuntos}

O seguinte modelo de representação de dados e relações para um sistema de diagnóstico foi proposto 
por \citet{Reggia83}. Segundo o modelo, podem-se abstrair os problemas de diagnóstico para o modelo 
teórico de cobertura de conjuntos. Temos então dois conjuntos discretos e finitos que definem o 
escopo dos problemas de diagnóstico: \textbf{D}, representando todos os possíveis transtornos $d_{i}$ que 
podem acontecer, e \textbf{M}, representando todas as possíveis manifestações $m_{j}$ que podem 
ocorrer devido à presença de um ou mais transtornos. Na medicina, podemos considerar \textbf{D} como 
o conjunto de todas as doenças conhecidas e \textbf{M} como o conjunto de todos os sintomas sendo, 
portanto, $\textbf{D} \cap \textbf{M} = \emptyset $.

A fim de capturar a noção intuitiva de causa, assume-se a existência de uma 
relação $\textbf{C} \subseteq \textbf{D} \times \textbf{M}$, 
onde $(d_{i}, m_{j}) \in \textbf{C}$ significa \textquotedblleft $d_{i}$ pode causar $m_{j} $\textquotedblright. Perceba que $(d_{i}, m_{j}) \in \textbf{C}$ não implica que $m_{j}$ sempre 
aconteça com a presença de $d_{i}$. Isso quer dizer que um paciente portador de uma doença não 
necessariamente possui todos os sintomas comuns daquela doença.

Dados \textbf{D}, \textbf{M} e \textbf{C}, pode-se ainda definir os seguintes conjuntos:
\[ man(d_{i}) = \{m_{j} \mid (d_{i}, m_{j}) \in \textbf{C}\} \: \forall \: d_{i} \in \textbf{D} \] e 
\[ causas(m_{j}) = \{ d_{i} \mid (d_{i}, m_{j}) \in \textbf{C}\} \: \forall \: m_{j} \in \textbf{M}. \]

Esses conjuntos, ilustrados na Figura~\ref{img:identificadores} (a), representam todas as possíveis manifestações causadas por $d_{i}$, e todos os possíveis transtornos que causam $m_{j}$, respectivamente. Esses conceitos são intuitivamente usados no processo de decisão de diagnóstico. Como exemplo, pode-se citar livros da literatura medicinal como \citet{McPhee10} que comumente oferecem descrições de doenças que possuem, entre outras coisas, o conjunto de manifestações $man(d_{i})$ para cada doença $d_{i}$. 

\begin{figure}[htb]
	\center
	\includegraphics[scale=0.8]{images/problemasdiagn.png}
	\caption{(a)Organização do conhecimento e (b)dos problemas \citep[p.~438]{Reggia83}.}
	\label{img:identificadores}
\end{figure}

Pode-se ainda definir o conjunto distinto $M^{+} \subseteq \textbf{M}$ como a representação das 
manifestações, as quais sabe-se que estão presentes (veja Figura~\ref{img:identificadores} (b)).  Portanto \textbf{D}, \textbf{M} e \textbf{C} são 
conhecimentos gerais sobre a classe de problemas de diagnóstico, enquanto $M^{+}$ representa as 
manifestações de um problema específico.

Com esta terminologia faz-se a seguinte definição:

\textit{Definição}. \citep[p.~438]{Reggia83} Um \textbf{problema de diagnóstico} ${P}$ é uma quádrupla $(\textbf{D}, \textbf{M}, \textbf{C}, M^{+})$ e o significado de seus componentes estão descritos nos parágrafos anteriores.

Com a caracterização dos problemas de diagnóstico nesses termos,
pode-se definir a solução de um problema de diagnóstico introduzindo
primeiro o conceito de explicação.

\textit{Definição}. \citep[p.~438]{Reggia83} Para um problema de diagnóstico ${P}$, ${E} \subseteq \textbf{D}$ é a
\textbf{explicação} para $M^{+}$ se: (i) $M^{+} \subseteq man({E})$, ou em palavras: ${E}$ cobre $M^{+}$; e (ii)
$\left|{E}\right| \leq \left|\textbf{D}\right|$ para qualquer outra cobertura de \textbf{D} sobre $M^{+}$, isto é, ${E}$ é mínimo.

Essa definição expressa o sentido intuitivo da \textbf{explicação} de um conjunto de manifestações. 
A parte (i) especifica que o conjunto de transtornos ${E}$ deve ser capaz de causar todas as 
manifestações em $M^{+}$ para ser considerada explicação para aquelas manifestações. No entanto, 
isso não é o suficiente: a parte (ii) especifica que ${E}$ também deve ser um dos conjuntos de menor 
cardinalidade possível. A parte (ii) reflete o Princípio da Parcimônia \citep{Sober81}: a explicação 
mais simples é preferível. Podemos com isso definir a solução de um problema de diagnóstico:

\textit{Definição}. \citep[p.~439]{Reggia83} A solução para um problema de diagnóstico ${P}$, designada por $Sol({P})$, é o conjunto de todas as explicações para $M^{+}$.

Um exemplo de aplicação desses conceitos para a solução de um problema de diagnóstico pode ser 
encontrado no \hyperref[apd:exemplo]{Apêndice A}.

\section{Descoberta de Conhecimento em Base de Dados (KDD)}
\label{02:sec:kdd}

Descoberta de conhecimento em base de dados é o processo não trivial de identificar informações válidas, novas, potencialmente úteis e que sejam padrões lógicos em um conjunto de dados \citep{Fayyad96}. Segundo \citet{Fayyad96}, o termo conhecimento refere-se a um nível qualitativo mais alto de informação que permite tanto afirmações conclusivas como projeções futuristas.

Tendo em vista a qualidade da informação final e, por ser um
processo, o processo de KDD possui um conjunto de passos que devem ser seguidos
para que a qualidade \textquotedblleft conhecimento\textquotedblright seja alcançada (vide Figura~\ref{img:etapaskdd}). 

\begin{figure}[htb]
	\center
	\includegraphics[scale=0.5]{images/etapaskdd.png}
	\caption{Síntese das etapas do processo de KDD \citep[p.~41]{Fayyad96}.}
	\label{img:etapaskdd}
\end{figure}

Os passos iniciais
consistem no tratamento e limpeza dos dados e são essenciais para a
qualidade do resultado final. Segue uma breve descrição de cada um dos
passos envolvidos no processo de KDD:

\begin{enumerate}
\item O primeiro passo consiste no entendimento do domínio da
aplicação, identificando os conhecimentos prioritários e o
objetivo do processo sobre o ponto de vista da aplicação;
\item O segundo é a criação de um conjunto de dados alvo:
selecionar o conjunto de dados, ou um subconjunto de variáveis
ou amostras sobre as quais uma descoberta pode ser feita;
\item Limpeza e pré-processamento dos dados. Operações básicas
incluem a remoção de ruídos (inconsistências), definição de
estratégias para tratamento de dados faltantes;
\item Redução e projeção dos dados: Encontrar recursos úteis para a
representação dos dados dependendo do objetivo da tarefa. O
objetivo é a redução do número de variáveis a serem
consideradas ou encontrar representações invariantes para os
dados;
\item Encontrar um método de mineração de dados que se enquadre
no objetivo do processo de KDD;
\item Análise e modelagem exploratórias e seleção de hipóteses:
escolher os algoritmos de mineração de dados e os métodos de
seleção para serem utilizados na procura de padrões de dados;
\item Aplicação da mineração de dados definida para a descoberta de
padrões interessantes;
\item Interpretação sobre os dados minerados para obtenção de
conhecimento. Esta etapa pode exigir o retorno para uma das
etapas anteriores a fim de tornar os resultados mais
consistentes;
\item Ação sobre o conhecimento descoberto, usando-o em uma
aplicação específica ou associando-o a um sistema
computacional para um determinado fim.
\end{enumerate}

\section{Mineração de dados no Processo de KDD}
\label{03:sec:mineracaokdd}

Segundo \citet{Fayyad96}, a mineração de dados no processo de KDD se resume na procura de padrões existentes. Geralmente, estabelecem-se modelos que definem o formato das informações obtidas ao final dessa etapa. Esses modelos exercem o papel do conhecimento inferido. Dois formalismos matemáticos podem ser utilizados para o uso desses modelos: estatístico e lógico. Destes, o único que oferece resultados não determinísticos é o estatístico e, portanto, costuma ser mais enriquecedor em termos de conhecimento. Além disso, é a abordagem mais amplamente utilizada em aplicações de mineração de dados.

Como dito anteriormente, o método de mineração de dados utilizado deve ser escolhido segundo as necessidades do processo de KDD como um todo. Os métodos estatísticos mais comuns são classificação, \textit{clustering} e regressão, e estes são baseados em técnicas de aprendizagem de máquina. Embora existam diferenças de abordagem, esses algoritmos costumam se apoiar em três componentes principais: representação do modelo, análise do modelo e busca.

A representação do modelo é a linguagem usada para descrever padrões que podem ser descobertos. A representação deve ser completa ao ponto de que os resultados modelados sejam precisos o suficiente e, ao mesmo tempo, deve ser limitada para evitar a modelagem exagerada de dados que não refletem a obtenção de conhecimento.

Os critérios de análise do modelo são definições quantitativas de quanto um modelo encaixa-se nos objetivos do processo de KDD. Este tipo de análise geralmente é feita através do dimensionamento de características ideais para o \textquotedblleft conhecimento\textquotedblright, como o grau de inovação, utilidade e possibilidade de entendimento de um modelo.

Uma vez estabelecidos a representação e os critérios de análise do modelo, o método de busca consiste de dois componentes principais: procura de parâmetros e procura de modelos. Na procura de parâmetros, o algoritmo deve procurar parâmetros que aperfeiçoem os critérios de análise do modelo, dado um conjunto de dados observados e uma representação estática do modelo. A procura de modelos ocorre de maneira iterativa sobre a procura de parâmetros: a representação do modelo é alterada para que uma família de representações seja considerada no processo.

\section{Métodos de Mineração de Dados}
\label{04:sec:metodosmineracao}

A escolha da técnica de mineração de dados a ser utilizada em uma aplicação prática deve levar em conta aspectos do objetivo que se deseja alcançar, e, ao mesmo tempo, características dos dados que se possui. Por exemplo, em aplicações em que não existe a necessidade de uma explicação simples do conhecimento obtido, o uso de técnicas de regressão não linear baseadas em lógica nebulosa ou Redes Neurais Artificiais, pode ser bem vindo. Da mesma forma, em uma massa de dados onde as informações são de naturezas muito diferentes, ou até mesmo conflitantes, talvez o uso de técnicas de agrupamento e classificação não seja adequado (veja \citet{Cheng94}, \citet{Friedman91} e \citet{Elder95} para discussões mais detalhadas).

Como este projeto de formatura depende de resultados concretos das próximas etapas para a definição da mineração de dados utilizada, é interessante manter nesta especificação um registro das possíveis técnicas para um aprofundamento posterior. Para facilitar o entendimento pode-se considerar um exemplo fictício de um banco, onde se tem um conjunto de dados de clientes que fizeram empréstimos. As informações dos clientes que estão sendo consideradas são a dívida total (como aluguel, prestações do carro, etc.) e a renda. Essas informações são representadas em forma de eixos de um gráfico ilustrados na Figura~\ref{img:ilustracao}. Os clientes são classificados em devedores, representados pelo símbolo \textquoteleft x\textquoteright, e aqueles que honraram seus empréstimos, representados pelo símbolo \textquoteleft o\textquoteright.

\begin{figure}[htb]
	\center
	\includegraphics[scale=0.6]{images/dm-grafico1.png}
	\caption{Conjunto de dados simples para ilustração \citep[p.~43]{Fayyad96}.}
	\label{img:ilustracao}
\end{figure}

\subsection{Classificação}
\label{01:subsec:classificacao}

A classificação consiste no aprendizado de uma função capaz de mapear (classificar) um item de dado em uma dentre várias classes pré-definidas. Um exemplo de aplicação para a classificação pode ser como na Figura~\ref{img:classificao}. Repare que existem duas regiões distintas de classificação com uma separação linear entre elas. O uso de desta separação, contudo, não permite uma divisão perfeita entre as classes, mas ainda assim o banco pode usar a classificação para decidir automaticamente a concessão de um empréstimo.

\begin{figure}[htb]
	\center
	\includegraphics[scale=0.6]{images/dm-grafico2.png}
	\caption{Classificação linear simples \citep[p.~44]{Fayyad96}.}
	\label{img:classificao}
\end{figure}

Obviamente que é comum uma situação real, ao contrário do exemplo com apenas dois eixos, envolver múltiplos eixos de relevância.

Um algoritmo de classificação em específico que será detalhado é o \textbf{1R} descrito por \citet{Witten05}. Ele cria uma regra para cada ocorrência no banco e testa qual a porcentagem de acerto desta regra no escopo dos dados de treinamento e origina uma certa quantidade de regras. As regras são assim aplicadas nos dados de testes, de onde se origina a taxa de erro delas. A sequencia de passos do algoritmo é descrita a seguir, definido em pseudocódigo por \citet{Witten05}:

\begin{tabbing}
\hspace{0.4cm} \= \hspace{0.4cm} \= \kill
Para cada atributo, \\
\> Para cada valor daquele atributo, gerar um regra como a seguir: \\
\> \>	contar qual a frequência que cada classe do atributo aparece. \\
\> \> selecionar a classe mais frequente. \\
\> \> gerar regra para o atributo-valor selecionado. \\
\> Calcular a taxa de erro de cada regra. \\
Utilizar como saída do algoritmo a regra com menor taxa de erro.
\end{tabbing}

\subsection{Regressão}
\label{01:subsec:regressao}

Regressão é o aprendizado de uma função capaz de mapear um item de dado para uma variável de predição com um valor real. Por sua característica de correlação entre diferentes variáveis, a regressão é mais voltada para obtenção de predições do que para a obtenção de descrições conclusivas. A Figura~\ref{img:regressao} mostra uma regressão linear simples onde a dívida total é transformada em uma função linear da renda. Pode-se notar que, neste caso, a regressão não é muito eficiente, pois a relação entre as duas variáveis é fraca.

\begin{figure}[htb]
	\center
	\includegraphics[scale=0.6]{images/dm-grafico3.png}
	\caption{Regressão linear simples \citep[p.~44]{Fayyad96}.}
	\label{img:regressao}
\end{figure}


\subsection{\textit{Clustering}}
\label{01:subsec:clustering}

\textit{Clustering} consiste em identificar conjuntos finitos de categorias para agrupamento dos itens de dados.  Esses conjuntos são chamados de \textit{clusters}. As categorias podem ser mutuamente exclusivas e completas ou podem consistir de uma representação mais rica e elaborada, como uma representação hierárquica ou de categorias sobrepostas. A Figura~\ref{img:cluster} mostra a possibilidade de \textit{clustering} em três conjuntos de dados. Note que existe a possibilidade de sobreposição de categorias, de forma que um item pode pertencer a mais de um \textit{cluster} ao mesmo tempo. Repare também que as classes citadas anteriormente não são mais conhecidas após o \textit{clustering}, uma vez que o símbolos \textquoteleft x\textquoteright$\,$ e os símbolos  \textquoteleft o\textquoteright$\,$ do gráfico foram todos substituídos por \textquoteleft +\textquoteright, de forma que o que separa um \textit{cluster} de outro é a densidade de probabilidade de pagamento de um empréstimo.

\begin{figure}[htb]
	\center
	\includegraphics[scale=0.6]{images/dm-grafico4.png}
	\caption{Definição simples de \textit{clustering} \citep[p.~45]{Fayyad96}.}
	\label{img:cluster}
\end{figure}

\subsection{\textit{Divisão de dados - Treinamento e Testes}}
\label{01:subsec:tenfolding}


Qualquer método de mineração de dados a ser utilizado deve ser treinado e testado com dados diferentes, e a divisão destes dados pode impactar a qualidade do algoritmo. Os dados de treinamento fazem o algoritmo gerar regras enquanto os dados de teste têm a finalidade de estimar o erro das regras em representar o relacionamento entre os atributos. 

Caso os dados de treinamento forem muito poucos, é possível que as regras geradas sejam insuficientes e muito imprecisas. Mas caso eles sejam em números exagerados, é possível que muitas regras sejam geradas representando dados ruidosos, diminuindo a taxa de acerto destas. Já com as regras de teste quanto mais dados houver mais precisa será o erro estimado, mas se houver muito poucos o erro estimado pode ficar longe do real podendo fazer as regras parecerem boas enquanto são ruins, ou vice-versa.

Uma forma bastante comum de realizar o processo de escolha dos dados, como descrito por \citet{Witten05} é denominado \textit{ten-fold} onde os dados são divididos em dez partes de mesmo tamanho, aleatoriamente. Uma destas partes é usada para testes enquanto as outras nove são utilizadas para treinamento, e depois de passar pelo algoritmo, gera-se o as regras e o erro desta divisão. Este processo é repetido dez vezes, onde todas as partes serão uma vez utilizadas como dados de teste, e dez valores de erros serão criados. As regras escolhidas como saída do algoritmo serão as que apresentarem a menor taxa de erro dentre todas as dez.
